SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Operator-precedence parser</title>

</head>

Operator-precedence parser

</h1>

</header>

In <a href="Computer_science" title="Computer science">computer science</a>, an operator-precedence parser is a <a href="Bottom-up_parsing" title="Bottom-up parsing">bottom-up parser</a> that interprets an <a href="Operator-precedence_grammar" title="Operator-precedence grammar">operator-precedence grammar</a>. For example, most <a href="Calculator" title="Calculator">calculators</a> use operator-precedence parsers to convert from the human-readable <a href="Infix_notation" title="Infix notation">infix notation</a> relying on <a href="Order_of_operations" title="Order of operations">order of operations</a> to a format that is optimized for evaluation such as <a href="Reverse_Polish_notation" title="Reverse Polish notation">Reverse Polish notation</a> (RPN).

<a href="Edsger_Dijkstra" class="mw-redirect" title="Edsger Dijkstra">Edsger Dijkstra</a>'s <a href="Shunting_yard_algorithm" title="Shunting yard algorithm">shunting yard algorithm</a> is commonly used to implement operator-precedence parsers.

<div class="mw-heading mw-heading2"><h2 id="Relationship_to_other_parsers">Relationship to other parsers</h2></div>

An operator-precedence parser is a simple <a href="Shift-reduce_parser" title="Shift-reduce parser">shift-reduce parser</a> that is capable of parsing a subset of <a href="LR_parser" title="LR parser">LR(1)</a> grammars. More precisely, the operator-precedence parser can parse all LR(1) grammars where two consecutive <a href="Nonterminal" class="mw-redirect" title="Nonterminal">nonterminals</a> and <a href="Empty_string" title="Empty string">epsilon</a> never appear in the right-hand side of any rule.

Operator-precedence parsers are not used often in practice; however they do have some properties that make them useful within a larger design. First, they are simple enough to write by hand, which is not generally the case with more sophisticated right shift-reduce parsers. Second, they can be written to consult an operator table at <a href="Run_time_(program_lifecycle_phase)" class="mw-redirect" title="Run time (program lifecycle phase)">run time</a>, which makes them suitable for languages that can add to or change their operators while parsing. (An example is <a href="Haskell_(programming_language)" class="mw-redirect" title="Haskell (programming language)">Haskell</a>, which allows user-defined infix operators with custom associativity and precedence; consequently, an operator-precedence parser must be run on the program after parsing of all referenced modules.)

<a href="Raku_(programming_language)" title="Raku (programming language)">Raku</a> sandwiches an operator-precedence parser between two <a href="Recursive_descent_parser" title="Recursive descent parser">recursive descent parsers</a> in order to achieve a balance of speed and dynamism. <a href="GNU_Compiler_Collection" title="GNU Compiler Collection">GCC</a>'s C and C++ parsers, which are hand-coded recursive descent parsers, are both sped up by an operator-precedence parser that can quickly examine arithmetic expressions. Operator-precedence parsers are also embedded within <a href="Compiler-compiler" title="Compiler-compiler">compiler-compiler</a>-generated parsers to noticeably speed up the recursive descent approach to expression parsing.<a href="#cite_note-Harwell2008-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Precedence_climbing_method">Precedence climbing method</h2></div>

The precedence climbing method is a compact, efficient, and flexible algorithm for parsing expressions that was first described by Martin Richards and Colin Whitby-Strevens.<a href="#cite_note-Richards1979-2">[2]</a>

An infix-notation expression grammar in <a href="EBNF" class="mw-redirect" title="EBNF">EBNF</a> format will usually look like this:

<div class="mw-highlight mw-highlight-lang-abnf mw-content-ltr" dir="ltr"><pre>expression ::= equality-expression

equality-expression ::= additive-expression ( ( '==' | '!=' ) additive-expression ) *

additive-expression ::= multiplicative-expression ( ( '+' | '-' ) multiplicative-expression ) *

multiplicative-expression ::= primary ( ( '*' | '/' ) primary ) *

primary ::= '(' expression ')' | NUMBER | VARIABLE | '-' primary

</pre></div>

With many levels of precedence, implementing this grammar with a predictive recursive-descent parser can become inefficient. Parsing a number, for example, can require five function calls: one for each non-terminal in the grammar until reaching primary.

An operator-precedence parser can do the same more efficiently.<a href="#cite_note-Harwell2008-1">[1]</a> The idea is that we can left associate the arithmetic operations as long as we find operators with the same precedence, but we have to save a temporary result to evaluate higher precedence operators. The algorithm that is presented here does not need an explicit stack; instead, it uses recursive calls to implement the stack.

The algorithm is not a pure operator-precedence parser like the Dijkstra shunting yard algorithm. It assumes that the primary nonterminal is parsed in a separate subroutine, like in a recursive descent parser.

<div class="mw-heading mw-heading3"><h3 id="Pseudocode">Pseudocode</h3></div>

The pseudocode for the algorithm is as follows. The parser starts at function parse_expression. Precedence levels are greater than or equal to 0.

<pre>parse_expression()

return parse_expression_1(parse_primary(), 0)

</pre>

<pre>parse_expression_1(lhs, min_precedence)

lookahead := peek next token

while lookahead is a binary operator whose precedence is >= min_precedence

op := lookahead

advance to next token

rhs := parse_primary ()

lookahead := peek next token

while lookahead is a binary operator whose precedence is greater

than op's, or a right-associative operator

whose precedence is equal to op's

rhs := parse_expression_1 (rhs, precedence of op + (1 if lookahead precedence is greater, else 0))

lookahead := peek next token

lhs := the result of applying op with operands lhs and rhs

return lhs

</pre>

Note that in the case of a production rule like this (where the operator can only appear once):

<div class="mw-highlight mw-highlight-lang-abnf mw-content-ltr" dir="ltr"><pre>equality-expression ::= additive-expression ( '==' | '!=' ) additive-expression

</pre></div>

the algorithm must be modified to accept only binary operators whose precedence is > min_precedence.

<div class="mw-heading mw-heading3"><h3 id="Example_execution_of_the_algorithm">Example execution of the algorithm</h3></div>

An example execution on the expression 2 + 3 * 4 + 5 == 19 is as follows. We give precedence 0 to equality expressions, 1 to additive expressions, 2 to multiplicative expressions.

parse_expression_1 (lhs = 2, min_precedence = 0)

<ul><li>the lookahead token is +, with precedence 1. the outer while loop is entered.</li>

<li>op is + (precedence 1) and the input is advanced</li>

<li>the lookahead token is *, with precedence 2. the inner while loop is entered. parse_expression_1 (lhs = 3, min_precedence = 2)</li></ul>

<dl><dd><ul><li>the lookahead token is *, with precedence 2. the outer while loop is entered.</li></ul>

<dl><dd><ul><li>op is * (precedence 2) and the input is advanced</li>

<li>the next token is +, with precedence 1. the inner while loop is not entered.</li>

<li>lhs is assigned 3*4 = 12</li>

<li>the next token is +, with precedence 1. the outer while loop is left.</li></ul></dd></dl>

<ul><li>12 is returned.</li></ul></dd></dl>

<ul><li>the lookahead token is +, with precedence 1. the inner while loop is not entered.</li>

<li>lhs is assigned 2+12 = 14</li>

<li>the lookahead token is +, with precedence 1. the outer while loop is not left.</li>

<li>op is + (precedence 1) and the input is advanced</li>

<li>the next token is ==, with precedence 0. the inner while loop is not entered.</li>

<li>lhs is assigned 14+5 = 19</li>

<li>the next token is ==, with precedence 0. the outer while loop is not left.</li>

<li>op is == (precedence 0) and the input is advanced</li>

<li>the next token is end-of-line, which is not an operator. the inner while loop is not entered.</li>

<li>lhs is assigned the result of evaluating 19 == 19, for example 1 (as in the C standard).</li>

<li>the next token is end-of-line, which is not an operator. the outer while loop is left.</li></ul>

1 is returned.

<div class="mw-heading mw-heading2"><h2 id="Pratt_parsing">Pratt parsing</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

Another precedence parser known as Pratt parsing was first described by <a href="Vaughan_Pratt" title="Vaughan Pratt">Vaughan Pratt</a> in the 1973 paper "Top Down Operator Precedence",<a href="#cite_note-3">[3]</a> based on <a href="Recursive_descent_parser" title="Recursive descent parser">recursive descent</a>. Though it predates precedence climbing, it can be viewed as a generalization of precedence climbing.<a href="#cite_note-4">[4]</a>

Pratt designed the parser originally to implement the <a href="CGOL" title="CGOL">CGOL</a> programming language, and it was treated in much more depth in a Masters Thesis under his supervision.<a href="#cite_note-5">[5]</a>

Tutorials and implementations:

<ul><li><a href="Douglas_Crockford" title="Douglas Crockford">Douglas Crockford</a> based the JavaScript parser in <a href="JSLint" title="JSLint">JSLint</a> on Pratt parsing.<a href="#cite_note-6">[6]</a></li>

<li>Comparison between Python implementations of precedence climbing and Pratt parsing: <a rel="nofollow" class="external text" href="http://www.oilshell.org/blog/2016/11/01.html">"Pratt Parsing and Precedence Climbing Are the Same Algorithm" (2016) by Andy Chu</a></li>

<li>Tutorial using <a href="Rust_(programming_language)" title="Rust (programming language)">Rust</a>: <a rel="nofollow" class="external text" href="https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html">"Simple but Powerful Pratt Parsing" (2020) by Aleksey Kladov</a></li>

<li>Tutorial using <a href="Rust_(programming_language)" title="Rust (programming language)">Rust</a>: <a rel="nofollow" class="external text" href="https://williamr.dev/posts/pratt-parsing/">"The Pratt Parsing Technique" (2024) by William Rågstad</a></li>

<li>Tutorial using <a href="Python_(programming_language)" title="Python (programming language)">Python</a>: <a rel="nofollow" class="external text" href="http://effbot.org/zone/simple-top-down-parsing.htm">"Simple Top-Down Parsing in Python" (2008) by Fredrik Lundh</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20150228044653/http://effbot.org/zone/simple-top-down-parsing.htm">Archived</a> 2015-02-28 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li>

<li>Tutorial using <a href="Java_(programming_language)" title="Java (programming language)">Java</a>: <a rel="nofollow" class="external text" href="http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/">"Pratt Parsers: Expression Parsing Made Easy" (2011) by Bob Nystrom, author of Crafting Interpreters</a></li>

<li>Implementation in <a href="C_Sharp_(programming_language)" title="C Sharp (programming language)">C#</a>: <a rel="nofollow" class="external text" href="https://github.com/atifaziz/Gratt">"Gratt: A Generic Vaughn Pratt's top-down operator precedence parser for .NET Standard"</a> (a <a href="Generic_programming" title="Generic programming">generic</a> version inspired by the Java implementation presented by Bob Nystrom in <a rel="nofollow" class="external text" href="http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/">"Pratt Parsers: Expression Parsing Made Easy"</a>)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Alternative_methods">Alternative methods</h2></div>

There are other ways to apply operator precedence rules. One is to build a tree of the original expression and then apply tree rewrite rules to it.

Such trees do not necessarily need to be implemented using data structures conventionally used for trees. Instead, tokens can be stored in flat structures, such as tables, by simultaneously building a priority list which states what elements to process in which order.

<div class="mw-heading mw-heading3"><h3 id="Full_parenthesization">Full parenthesization</h3></div>

Another approach is to first fully parenthesize the expression, inserting a number of parentheses around each operator, such that they lead to the correct precedence even when parsed with a linear, left-to-right parser. This algorithm was used in the early <a href="Fortran#FORTRAN" title="Fortran">FORTRAN I</a> compiler:<a href="#cite_note-Padua2000-7">[7]</a>

The Fortran I compiler would expand each operator with a sequence of parentheses. In a simplified form of the algorithm, it would

<ul><li>replace <code>+</code> and <code>–</code> with <code>))+((</code> and <code>))-((</code>, respectively;</li>

<li>replace <code>*</code> and <code>/</code> with <code>)*(</code> and <code>)/(</code>, respectively;</li>

<li>add <code>((</code> at the beginning of each expression and after each left parenthesis in the original expression; and</li>

<li>add <code>))</code> at the end of the expression and before each right parenthesis in the original expression.</li></ul>

Although not obvious, the algorithm was correct, and, in the words of <a href="Donald_Knuth" title="Donald Knuth">Knuth</a>, “The resulting formula is properly parenthesized, believe it or not.”<a href="#cite_note-Knuth1962-8">[8]</a>

</blockquote>

Example code of a simple C application that handles parenthesisation of basic math operators (<code>+</code>, <code>-</code>, <code>*</code>, <code>/</code>, <code>^</code>, <code>(</code> and <code>)</code>):

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>#include <stdio.h>

#include <string.h>

// The command-line argument boundary is our lexer.

int main(int argc, char *argv[]) {

int i;

printf("((((");

for (i=1; i!=argc; i++) {

// strlen(argv[i]) == 2

if (argv[i] && !argv[i][1]) {

switch (*argv[i]) {

case '(': printf("(((("); continue;

case ')': printf("))))"); continue;

case '^': printf(")^("); continue;

case '*': printf("))*(("); continue;

case '/': printf("))/(("); continue;

case '+':

// unary check: either first or had an operator expecting secondary argument

if (i == 1 || strchr("(^*/+-", *argv[i-1]))

printf("+");

else

printf(")))+(((");

continue;

case '-':

printf("-");

else

printf(")))-(((");

continue;

}

printf("%s", argv[i]);

}

printf("))))\n");

return 0;

}

</pre></div>

First, you need to compile your program. Assuming your program is written in C and the source code is in a file named program.c, you would use the following command:

<pre>gcc program.c -o program</pre>

The above command tells gcc to compile program.c and create an executable named program.

Command to run the program with parameters, For example; a * b + c ^ d / e

<pre>./program a '*' b + c '^' d / e</pre>

it produces

as output on the console.

A limitation to this strategy is that unary operators must all have higher precedence than infix operators. The "negative" operator in the above code has a higher precedence than exponentiation. Running the program with this input

produces this output

which is probably not what is intended.

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFHarwell2008" class="citation web cs1">Harwell, Sam (2008-08-29). <a rel="nofollow" class="external text" href="https://theantlrguy.atlassian.net/wiki/spaces/ANTLR3/pages/2687077/Operator+precedence+parser">"Operator precedence parser"</a>. ANTLR3 Wiki. Retrieved 2017-10-25.</cite>

</li>

<li id="cite_note-Richards1979-2"><a href="#cite_ref-Richards1979_2-0">^</a> <cite id="CITEREFRichardsWhitby-Strevens1979" class="citation book cs1">Richards, Martin; Whitby-Strevens, Colin (1979). BCPL — the language and its compiler. Cambridge University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780521219655</bdi>.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> Pratt, Vaughan. "<a rel="nofollow" class="external text" href="https://web.archive.org/web/20151223215421/http://hall.org.ua/halls/wizzard/pdf/Vaughan.Pratt.TDOP.pdf">Top Down Operator Precedence</a>." Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (1973).

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFNorvell" class="citation web cs1">Norvell, Theodore. <a rel="nofollow" class="external text" href="http://www.engr.mun.ca/~theo/Misc/pratt_parsing.htm">"Parsing Expressions by Recursive Descent"</a>. www.engr.mun.ca. <q>The purpose of this post is to [... start] with precedence climbing and refactoring it to use the command pattern until we arrive at a Pratt parser. [This is the author who coined the term "precedence climbing".]</q></cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> Van De Vanter, Michael L. "<a rel="nofollow" class="external text" href="http://publications.csail.mit.edu/lcs/specpub.php?id=715">A Formalization and Correctness Proof of the CGOL Language System</a>." (Master's Thesis). MIT Laboratory for Computer Science Technical Report MIT-LCS-TR-147 (Cambridge, Massachusetts). 1975.

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFCrockford,_D2007" class="citation web cs1">Crockford, D (2007-02-21). <a rel="nofollow" class="external text" href="http://crockford.com/javascript/tdop/tdop.html">"Top Down Operator Precedence"</a>.</cite>

</li>

<li id="cite_note-Padua2000-7"><a href="#cite_ref-Padua2000_7-0">^</a> <cite id="CITEREFPadua2000" class="citation journal cs1">Padua, David (2000). <a rel="nofollow" class="external text" href="http://polaris.cs.uiuc.edu/publications/c1070.pdf">"The Fortran I Compiler"</a> (PDF). Computing in Science & Engineering. 2 (1): 70–75. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2000CSE.....2a..70P">2000CSE.....2a..70P</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F5992.814661">10.1109/5992.814661</a>.</cite>

</li>

<li id="cite_note-Knuth1962-8"><a href="#cite_ref-Knuth1962_8-0">^</a> <cite id="CITEREFKnuth1962" class="citation journal cs1">Knuth, Donald E. (1962). <a rel="nofollow" class="external text" href="https://archive.org/details/bitsavers_computersA_13990695">"A HISTORY OF WRITING COMPILERS"</a>. Computers and Automation. 11 (12). Edmund C. Berkeley: 8–14.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><cite id="CITEREFClarke1992" class="citation web cs1">Clarke, Keith (1992-05-26). <a rel="nofollow" class="external text" href="https://groups.google.com/group/comp.compilers/browse_thread/thread/aee24b9504d527ca/1210ef8ae529accd#1210ef8ae529accd">"Re: compact recursive-descent parsing of expressions"</a>. Retrieved 2012-01-24.</cite></li>

<li><a rel="nofollow" class="external text" href="https://groups.google.com/group/comp.compilers/browse_thread/thread/442ca111b2dfb38d/5390237263b3625b#5390237263b3625b">Example C++ code by Keith Clarke for parsing infix expressions using the precedence climbing method</a></li>

<li><cite id="CITEREFSamelsonFriedrich_L._Bauer1960" class="citation journal cs1"><a href="Klaus_Samelson" title="Klaus Samelson">Samelson, Klaus</a>; <a href="Friedrich_L._Bauer" title="Friedrich L. Bauer">Friedrich L. Bauer</a> (February 1960). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F366959.366968">"Sequential formula translation"</a>. Communications of the ACM. 3 (2): 76–83. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F366959.366968">10.1145/366959.366968</a>.</cite></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20160817143616/http://radovan-augustin.info/techpapers/parser/Parser.pdf">Parser for expression with infix notation using precedence lists</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Parsing_algorithms116" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Parsing_algorithms116" style="font-size:114%;margin:0 4em"><a href="Parsing" title="Parsing">Parsing algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Top-down_parsing" title="Top-down parsing">Top-down</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Earley_parser" title="Earley parser">Earley</a></li>

<li><a href="Recursive_descent_parser" title="Recursive descent parser">Recursive descent</a>

<ul><li><a href="Tail_recursive_parser" title="Tail recursive parser">Tail recursive</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Bottom-up_parsing" title="Bottom-up parsing">Bottom-up</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>Precedence

<ul><li><a href="Simple_precedence_parser" title="Simple precedence parser">Simple</a></li>

<li>

<ul><li><a href="Shunting_yard_algorithm" title="Shunting yard algorithm">Shunting-yard</a></li></ul></li></ul></li>

<ul><li><a href="Simple_LR_parser" title="Simple LR parser">Simple</a></li>

<li><a href="LALR_parser" title="LALR parser">Look-ahead</a></li>

<li><a href="Canonical_LR_parser" title="Canonical LR parser">Canonical</a></li>

<li><a href="GLR_parser" title="GLR parser">Generalized</a></li></ul></li>

<li><a href="Recursive_ascent_parser" title="Recursive ascent parser">Recursive ascent</a></li>

<li><a href="Shift-reduce_parser" title="Shift-reduce parser">Shift-reduce</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Mixed, other</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Parser_combinator" title="Parser combinator">Combinator</a></li>

<li><a href="Chart_parser" title="Chart parser">Chart</a>

<ul><li><a href="Left_corner_parser" title="Left corner parser">Left corner</a></li></ul></li>

<li>Statistical</li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related topics</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Definite_clause_grammar" title="Definite clause grammar">Definite clause grammar</a></li>

<li><a href="Deterministic_parsing" title="Deterministic parsing">Deterministic parsing</a></li>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="Memoization" title="Memoization">Memoization</a></li>

<li><a href="Compiler-compiler" title="Compiler-compiler">Parser generator</a>

<li><a href="Parse_tree" title="Parse tree">Parse tree</a></li>

<li><a href="Scannerless_parsing" title="Scannerless parsing">Scannerless parsing</a></li>

<li><a href="History_of_compiler_construction" title="History of compiler construction">History of compiler construction</a></li>

<li><a href="Comparison_of_parser_generators" title="Comparison of parser generators">Comparison of parser generators</a></li>

<li><a href="Operator-precedence_grammar" title="Operator-precedence grammar">Operator-precedence grammar</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-05" href="https://en.wikipedia.org/wiki/?title=Operator-precedence_parser&oldid=1278940100">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>